package com.wm.algorithm.linked;

import com.wm.algorithm.linked.entity.ListNode;

/**
 * @Classname MediumLinked
 * @Description 中等链表题
 * @Date 2022/1/26 11:33
 * @Created by WM
 */
public class MediumLinked {

    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        ListNode tmpNode = head;
        System.out.println("转换之前：");
        while (head != null) {
            System.out.print(head.val + "\t");
            head = head.next;
        }
        ListNode newNode = swapPairs(tmpNode);
        System.out.println();
        System.out.println("转换之后：");
        while (newNode != null) {
            System.out.print(newNode.val + "\t");
            newNode = newNode.next;
        }
    }

    /**
     * 61. 旋转链表
     * https://leetcode.cn/problems/rotate-list/description/
     * 方法：闭合为环
     * 思路：首先是参数校验，head和k。然后计算出链表的长度，k和长度进行取模赋值给k，将此时遍历的链表尾部节点指向
     * 头节点，这样就形成的一个闭环的链表，从尾结点先后移动length-k步(跳了多少步)，找到新的尾部和新的头节点，
     * 将新的头节点赋值给一个新的节点，此时获取的就是新链表的头节点，将新节点的上一个节点指针指向null即可，其实
     * 就是断开链表。
     *
     * @param head
     * @param k
     * @return
     */
    // O(n)/O(1)
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k <= 0) {
            return head;
        }
        // 计算链表长度
        int len = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            len++;
        }
        // k对链表长度取模，得到实际需要移动的位置
        k = k % len;

        // 找到新的尾部和新的头部
        tail.next = head;// 将链表首尾相连形成环
        int skipStep = len - k;
        for (int i = 0; i < skipStep; i++) {
            tail = tail.next;
        }
        // 新的头节点
        ListNode newNode = tail.next;
        // 断开旧的链接，恢复原来的链表结构
        tail.next = null;
        return newNode;
    }

    /**
     * 143. 重排链表
     * https://leetcode.cn/problems/reorder-list/description/
     * 方法：寻找链表中点 + 链表逆序 + 合并链表
     * 思路：首先通过快慢指针找到链表的中点，然后翻转中点之后的半个链表，然后将两个链表进行合并。合并的过程中先是将两个链表的
     * 当前的节点的下一个节点先提前进行保存，然后将l1链表的下一个节点指向l2的当前的节点，然后两个节点进行前移，也就是直接赋值
     * 之前的保存的节点即可
     *
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        // 获取中间节点
        ListNode mid = getMidNode(head);
        ListNode l1 = head, l2 = mid.next;
        // 这里需要注意：是需要把后半截直接置空的，原链表去除后半部分，即l1成为mid的前半部分（包含mid）
        mid.next = null;
        // 翻转后半个链表
        l2 = traverse(l2);
        // 合并两个链表
        mergerList(l1, l2);
    }

    private ListNode getMidNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode traverse(ListNode root) {
        ListNode pre = null, cur = root;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private void mergerList(ListNode l1, ListNode l2) {
        ListNode l1Next, l2Next;
        while (l1 != null && l2 != null) {
            l1Next = l1.next;
            l2Next = l2.next;

            l1.next = l2;
            l1 = l1Next;

            l2.next = l1;
            l2 = l2Next;
        }
    }


    /**
     * 92. 反转链表 II
     * https://leetcode.cn/problems/reverse-linked-list-ii/
     * 方法：递归
     * 思路：我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？
     * 那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的。然后依次类推
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    // O(n)/O(n)
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    // 反转链表的前N个节点
    ListNode successor = null;

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        // 连接头节点
        head.next.next = head;
        head.next = successor;
        return last;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
     * 方法：双指针（快慢指针）
     * 思路：先找到倒数第n+1个位置的数，然后链接到被删除元素的下一个节点
     *
     * @param head
     * @param n
     * @return
     */
    // O(n)/O(1)
    public ListNode removeNthFromEnd3(ListNode head, int n) {
        // 使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，
        // 题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。
        // 但第一个节点前面已经没有节点了，这就会出错。
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = findFromEnd(dummy, n + 1);
        pre.next = pre.next.next;
        return dummy.next;
    }

    // 查找链表的倒数第k个节点
    // 思路：首先要清楚，倒数走k步的位置是正数走n-k+1的位置。
    // 一次遍历，p1指针先走k步，p2指针指向第一个节点，然后两个指针一起前进，p1走n-k步完成，p2继续也走n-k步，然后到达n-k+1的位置
    private ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1先走k步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1和p2同时走n-k步
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    /**
     * 24. 两两交换链表中的节点
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 方法2：迭代
     * tmp>node1>node2  变为  tmp>node2>node1
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode swapPairs2(ListNode head) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode tmp = dummyNode;
        while (tmp.next != null && tmp.next.next != null) {
            ListNode node1 = tmp.next;
            ListNode node2 = tmp.next.next;
            tmp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            tmp = node1;
        }
        return dummyNode.next;
    }

    /**
     * 24. 两两交换链表中的节点
     * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
     * 方法1：递归
     */
    // 时间复杂度：O(n) 空间复杂度：O(n)
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
     * 方法2：双指针
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        // 快指针比慢指针快走n步，fast走到最终，slow此时走到的是要删除元素的之前一个元素
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 快慢指针相隔n个节点，倒数第n个节点是fast指向null，slow.next
        ListNode fast = head;
        ListNode slow = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 这里是fast!=null 保证slow.next.next不报错
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
     * 方法1：遍历+虚拟节点
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 首先计算数链表的总数量count，count-n即要删除的链表元素
        // 加虚拟节点
        ListNode firstNode = new ListNode(0);
        firstNode.next = head;
        int count = 1;
        ListNode tmp = firstNode;
        while (tmp.next != null) {
            count++;
            tmp = tmp.next;
        }
        count = count - n;
        // 使将要删除的元素被后一个元素覆盖
        int i = 0;
        tmp = firstNode;
        // 加虚拟节点 防止只有一个元素的情况下，删除的时候此处不通用直接报错
        while (tmp.next != null) {
            i++;
            if (i == count) {
                tmp.next = tmp.next.next;
            } else {
                tmp = tmp.next;
            }
        }
        return firstNode.next;
    }

    /**
     * 2、两数相加
     *
     * @param node1
     * @param node2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode node1, ListNode node2) {
        ListNode result = null, curr = null;
        int jinNum = 0;
        while (node1 != null || node2 != null) {
            int num1 = node1 != null ? node1.val : 0;
            int num2 = node2 != null ? node2.val : 0;
            int sum = num1 + num2 + jinNum;
            if (result == null) {//第一次存值
                result = curr = new ListNode(sum % 10);//之前的问题卡在这了result = curr curr引用给了result
            } else {
                curr.next = new ListNode(sum % 10);
                curr = curr.next;
            }
            jinNum = sum / 10;
            if (jinNum > 0) {
                curr.next = new ListNode(jinNum);
            }
            if (node1 != null) {
                node1 = node1.next;
            }
            if (node2 != null) {
                node2 = node2.next;
            }
        }
        return result;
    }
}
